package algotithm.weekendrace.leetcode226.test2;


import java.util.HashMap;
import java.util.HashSet;

/**
 * @author zhouyanxiang
 * @Date 2021-01-2021/1/31-10:16
 * @Title 5665. 从相邻元素对还原数组
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] aps = {{2,1},{3,4},{3,2}};
        int[] array = solution.restoreArray(aps);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    public int[] restoreArray(int[][] aps) {
        HashMap<Integer, HashSet<Integer>> g = new HashMap<>();
        int n = aps.length+1;
        int[] ans = new int[n];
        for (int[] ap : aps) {
            int u = ap[0];
            int v = ap[1];
            if (!g.containsKey(u)) {
                g.put(u, new HashSet<>());
            }
            if (!g.containsKey(v)) {
                g.put(v, new HashSet<>());
            }
            g.get(u).add(v);
            g.get(v).add(u);
        }
        int first = -1;
        for (int k : g.keySet()) {
            if (g.get(k).size()==1) {
                first = k;
            }
        }
        ans[0] = first;
        for (int i = 1; i < n; ++i) {
            ans[i] = g.get(ans[i-1]).iterator().next();
            g.get(ans[i]).remove(ans[i-1]);
        }
        return ans;
    }
}
